package algorithm.util;

import java.math.BigDecimal;
import java.util.List;

public class AdvMath {

	public static BigDecimal gcd(BigDecimal m, BigDecimal n) {

		m = m.abs();
		n = n.abs();
		if (m.equals(BigDecimal.ZERO)) {
			return n;
		} else if (n.equals(BigDecimal.ZERO)) {
			return m;
		} else if (m.compareTo(n) > 0) {
			return gcd(n, m.remainder(n));
		} else if (m.compareTo(n) < 0) {
			return gcd(m, n.remainder(m));
		} else {
			return m;
		}
	}
	
	public static BigDecimal gcd(List<BigDecimal> l) {
		
		if (l != null) {
			BigDecimal gcd = l.get(0);
			for (int i = 1; i < l.size(); i ++) {
				gcd = gcd(gcd, l.get(i));
			}
			return gcd;
		} else {
			return BigDecimal.ZERO;
		}
	}

	public static BigDecimal lcd(BigDecimal m, BigDecimal n) {
		
		m = m.abs();
		n = n.abs();
		if (m.equals(BigDecimal.ZERO) || n.equals(BigDecimal.ZERO)) {
			return BigDecimal.ZERO;
		} else {
			BigDecimal gcd = gcd(m,n);
			return m.divide(gcd).multiply(n);
		}
	}
	
	public static BigDecimal lcd(List<BigDecimal> l) {
		
		if (l != null) {
			BigDecimal lcd = l.get(0);
			for (int i = 1; i < l.size(); i ++) {
				lcd = lcd(lcd, l.get(i));
			}
			return lcd;
		} else {
			return BigDecimal.ZERO;
		}
	}
	
	/**
	 * C(m,n)
	 * @param m
	 * @param n
	 */
	public static BigDecimal combine(BigDecimal m, BigDecimal n) {
		
		if (m.compareTo(BigDecimal.ZERO) < 0 || n.compareTo(BigDecimal.ZERO) < 0) {
			return BigDecimal.ZERO;
		} else if (n.compareTo(m) > 0) {
			return BigDecimal.ZERO;
		} else if (n.compareTo(m.divide(BigDecimal.valueOf(2))) > 0) {
			return combine(m, m.subtract(n));
		} else {
			BigDecimal r = BigDecimal.ONE;
			BigDecimal i = BigDecimal.ZERO;
			while (i.compareTo(n) < 0) { 
				r = r.multiply(m.subtract(i));
				i = i.add(BigDecimal.ONE);
				r = r.divide(i);
			}
			return r;
		}
	}

	/**
	 * (m_1+...+m_n)!/(m_1!m_2!...m_n!)
	 * @param ms
	 * @return
	 */
	public static BigDecimal combine(BigDecimal... ms) {

		if (ms == null || ms.length == 0) {
			return BigDecimal.ZERO;
		} else {
			BigDecimal sum = BigDecimal.ZERO;
			for (BigDecimal m : ms) {
				if (m.compareTo(BigDecimal.ZERO) < 0) {
					return BigDecimal.ZERO;
				} else {
					sum = sum.add(m);
				}
			}
			BigDecimal r = BigDecimal.ONE;
			BigDecimal i, j = sum;
			for (BigDecimal m : ms) {
				i = BigDecimal.ZERO;
				while (i.compareTo(m) < 0) {
					r = r.multiply(j);
					j = j.subtract(BigDecimal.ONE);
					i = i.add(BigDecimal.ONE);
					r = r.divide(i);
				}
			}
			return r;
		}
	}
}
